import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/16
 * \* Time: 18:43
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 划分为k个相等的子集 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        //排除一些基本情况
        if(k>nums.length){
            return false;
        }
        int sum=0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%k!=0){
            return false;
        }
        //将数组按从大到小排序，加快剪枝速度
        Arrays.sort(nums);
        int i = 0, j = nums.length - 1;
        for (; i < j; i++, j--) {
            // 交换 nums[i] 和 nums[j]
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        // k 个桶（集合），记录每个桶装的数字之和
        int[] bucket=new int[k];
        int target=sum/k;
        return backtrace(nums,0,bucket,target);
    }

    boolean backtrace(int[] nums,int index,int[] bucket,int target){
        //结束条件，检查每个桶里面的数是否都等于target
        if(index== nums.length){
            for(int i=0;i< bucket.length;i++){
                if(bucket[i]!=target){
                    return false;
                }
            }
            return true;
        }

        // 穷举 nums[index] 可能装入的桶
        for(int i=0;i< bucket.length;i++){
            // 剪枝，桶装装满了
            if(bucket[i]+nums[index]>target){
                continue;
            }
            // 将 nums[index] 装入 bucket[i]
            bucket[i]+=nums[index];
            // 递归穷举下一个数字的选择
            if(backtrace(nums,index+1,bucket,target)){
                return true;
            }
            // 撤销选择
            bucket[i] -= nums[index];
        }
        // nums[index] 装入哪个桶都不行
        return false;
    }
}